The present invention relates to wireless communication networks. More particularly, the present invention relates to the provision of an effective routing scheme incorporating Low Earth Orbit (LEO) satellites to provide a reliable broadband communication network.
Terrestrial wireless networks such as cellular and personal communication system (PCS) networks are currently used to provide mobile communications services, and have limited geographic coverage. Low Earth Orbit (LEO) satellite networks can be used to augment these terrestrial wireless networks in order to provide global broadband services to users regardless of the users"" geographical locations. Because of the low altitude of LEO satellites, the round trip propagation delay for communication between an Earth-based terminal and a LEO satellite is comparable to the round trip communication time in terrestrial networks. Thus, real-time communications services can be delivered to users in diverse geographic locations. A LEO is defined as any earth orbit of up to approximately 1,500 kilometers in altitude. At this altitude, satellites typically orbit the earth in periods of approximately 100 to 120 minutes. For reference, examples of several classes of earth orbits, including LEOs, medium earth orbits, and geosynchronous earth orbits are shown as elements 100, 102, and 104, respectively, in FIG. 1. With regard to LEO satellites, low elevation angles result in attenuation and terrain shadowing effects that place limits on reliable communication. Thus, LEO satellites must rely on high elevation angles for successful communication, resulting in a relatively small satellite footprint for each satellite. Thus, in order to provide continuous and seamless services to users regardless of where a particular user is located, LEO satellite networks must include satellite constellations with tens of satellites. Additionally, the satellites must be equipped with capabilities such as on-board processing and inter-satellite communication links in order to provide a framework for robust and efficient communications.
LEO satellite systems currently under various phases of deployment maintain either Earth-fixed cells or they maintain satellite-fixed cells. Earth-fixed cells are stationary cells on the Earth that are dynamically served by LEO satellites cycling in and out of range of the cell. Satellite-fixed cells are dynamic cells formed from moving satellite footprints on the Earth, wherein the affiliation of as stationary individual user changes from cell to cell over time. A pictorial representation of two LEO satellites 200 is depicted in FIG. 2 with satellite-fixed cells 202. Issues involved with Earth-fixed cells, are similar to those involved in building terrestrial cellular networks.
In satellite networks with Earth-fixed cells, the mobility of terrestrial users causes a need for communication handovers, wherein a communication link is handed from one cell to another. In contrast, in satellite-fixed cells, the mobility of the satellites causes the need for communication handovers. Furthermore, in LEO satellite systems with satellite-fixed cells, the number of users in a cell and the traffic served by each satellite change over time. A user typically may be handed from one satellite to another multiple times over the duration of a single connection. The inherent mobility of the satellites may cause problems in maintaining user connections. For example, an ongoing connection may be dropped during handoff because of the lack of an available user-to-satellite uplink/downlink channel. If a particular connection has strict Quality of Service (QoS) requirements such as delay or delay jitter bounds, it may be blocked, even if user-to-satellite channels are available, due to the lack of a route with adequate resources between the satellite ingress and egress points.
The provisioning of guaranteed service relies on the reservation of a specific amount of bandwidth for a connection on the links connecting the communicating end-users. For example, in terrestrial broadband networks, a route for a particular connection requiring dedicated bandwidth, between two end-users is determined based on available bandwidth on various network links at the time of call set-up. Typically, when guaranteed services are offered, a particular route is used for the entire call duration. In LEO satellite networks, the traffic on the inter-satellite links (ISLs) changes with changes in the user-to-satellite traffic (which in turn changes due to the mobility of the satellites). Hence, traditional terrestrial routing methods cannot be applied to broadband LEO satellite networks. Although sufficient bandwidth may be available on a particular route at the time of call set-up for a particular call, the same route may become congested in time due to the changes in access traffic loads, which, in turn, change due to the mobility of the satellites.
Summarizing, delivering quality of service (QoS) guarantees to the users of LEO satellite networks is complicated, since footprints of LEO satellites move as the satellites traverse their orbits, thus causing frequent user handovers between satellites. Traffic on inter-satellite links of a particular satellite are subjected to changes as the user traffic served by the satellite changes with the satellite""s mobility. The change in user traffic on the inter-satellite links may cause violation of the QoS guarantees made to on-going calls.
As the traffic types increase to include real-time voice and video, it becomes essential to provide strict QoS bounds. Routing methods presently deployed in LEO satellite networks are based on Internet protocol (IP) routing, and cannot provide strict QoS bounds. Generally, these methods are negligent in taking into account the geographical distribution of the user traffic, and may result in the blocking of ongoing calls during handover attempts. Channel partitioning and bandwidth reservation schemes used for terrestrial cellular systems may be used to avoid handover call blocking at the expense of underutilization of channel bandwidth.
A major focus in LEO satellite network research has been toward the provision of successful signal handover to users of satellite-fixed cells as they transition from the coverage area of one satellite to the coverage area of another. This issue has been addressed, taking into account the fact that the same or different satellites may cover different users at different times. Research has also focused on setting up routes between pairs of satellites to minimize the re-routing frequency due to handovers, taking into account the fact that, often, due to satellite movement, a user pair might not be serviced by the same satellite end nodes for the complete call duration. However, an optimal route between two satellite nodes is not necessarily optimal for a connection between two ground terminals, since the handovers between the ground terminals and the satellites result in changing satellite end nodes for the connection.
The handover rerouting problem has been addressed in the context of terrestrial wireless networks, wherein the cells and the base stations serving those cells are stationary. The handover rerouting problem in this case arises due to the mobility of the end-users rather than that of the base stations. One proposed solution to the handover rerouting problem in terrestrial networks was to determine a whole new route after a handover. This solution, though optimal for a particular connection, causes excessive signaling in the network, resulting in a degradation of network throughput. Partial rerouting schemes have been proposed, wherein choosing a non-optimal path for the connection reduces the processing and messaging overhead in the network. Furthermore, it has been proposed that a new path for a connection during a handover be found by using as much of the original path used by the connection as possible. However, the resulting path connection found from source to destination is non-optimal.
Therefore, there is a need for a method for routing with guaranteed quality of service in a LEO satellite network which effectively handles handover rerouting.
A large amount of background information exists regarding satellite networks, including details of satellite network models such as the fluid model as well as means for implementing satellite network models, see e.g.:
A. Jamalipour, Low Earth Orbital Satellites for Personal Communication Networks, Artech House, Inc, 1998;
M. A. Sturza. xe2x80x9cArchitecture of the TELEDESIC Satellite System,xe2x80x9d Proceedings of International Mobile Satellite Conference, p.p. 212-218, 1995;
F. Dosiere, T. Zein, G. Maral, and J. P. Boutes. xe2x80x9cA Model for the Handover Traffic in Low-Earth Orbiting (LEO) Satellite Networks for Personal Communications,xe2x80x9d International Journal of Satellite Communications, 11: 145-149, 1993;
E. Del Re, R. Fantacci, and G. Giambene. xe2x80x9cHandover Requests Queuing in Low Earth Orbit Mobile Satellite Systems,xe2x80x9d Proceedings of the 2nd European Workshop on Mobile/Personal Satcoms, p.p. 213-232, 1996;
M. Werner, C. Delucchi, H.-J. Vogel, G. Maral, and J.-J. De Ridder. xe2x80x9cATM-Based Routing in LEO/MEO Satellite Networks with Intersatellite Links,xe2x80x9d IEEE Journal on Selected Areas in Communications, 15(1):69-82, January 1997;
B. A. Akyol and D. C. Cox. xe2x80x9cRerouting for Handoff in a Wireless ATM Networks,xe2x80x9d IEEE Personal Communications, 3(5):26-33, October 1996;
K. Y. Eng et al. xe2x80x9cA Wireless Broadband Ad-Hoc ATM Local Area Network,xe2x80x9d Wireless Networks, 1(2):161-174, 1995;
J. F. P. Labourdette and A. S. Acampora, xe2x80x9cLogically Rearrangable Multihop Lightwave Networks,xe2x80x9d IEEE Transactions Communications, vol.39, no. 8, pp.1223-1230, August 1991;
H. Uzunalioglu, W. Yen, and I. F. Akyildiz, xe2x80x9cA Connection Handover Protocol for LEO Satellite ATM Networksxe2x80x9d. Proc. of ACM Mobicom ""97, Budapest, Hungary, September 97;
S. Shenker, C. Partridge and R. Guerin, xe2x80x9cSpecification of Guaranteed Quality of Service,xe2x80x9d RFC 2212;
VINT Network Simulator (ns), version 2.0. University of California, Berkeley, Lawrence Berkeley National Laboratories, 1998, http:://mash.cs.berkeley.edu/ns/ns.html;
D. P. Connors, B. Ryu, and S. K. Dao, xe2x80x9cModeling and Simulation of Broadband Satellite Networks Part I: Medium Access Control for QoS Provisioning,xe2x80x9d IEEE Communications Magazine, March 99;
P. Ferguson and G. Huston, xe2x80x9cQuality of Service: Delivering QoS on the Internet and in Corporate Networks,xe2x80x9d Chap. 7, John Wiley and Sons, Inc. 1998; and
T. Le-Ngoc and S. V. Krishnamurthy, xe2x80x9cPerformance of Combined Free/Demand Assignment Multiple-Access Schemes in Satellite Communications,xe2x80x9d Int""l. Journal of Satellite Communication, Vol. 14, pp. 11-21 1996.
It is an object of the present invention to overcome the limitations discussed above, and to provide a method and apparatus for enabling predictive QoS routing of calls within a satellite network, with the method including the steps of:
a. providing a satellite constellation orbiting the earth, said satellite constellation including at least one orbit, with each one of the at least one orbit including a plurality S of satellites, each indexed by a number s, and communicatively connected by a plurality of communication links, with each particular satellite having a satellite-fixed cell divided, perpendicularly with respect to the orbit of the particular satellite, into a plurality L of satellite-fixed, cell slots, with the movement of the plurality S of satellites over the earth being characterized in that the satellite-fixed cell for a satellite indexed at s covers the same area as the satellite-fixed cell of a satellite indexed at s+1 after passing over an area on the earth equivalent to the area of L satellite-fixed cell slots, and with an offset satellite-fixed cell being defined each time the satellite-fixed cell covers the area of one of L satellite-fixed cell slots while moving between the position of the satellite-fixed cell corresponding to a satellite indexed s and the satellite-fixed cell corresponding to a satellite indexed s+1, providing L offset satellite-fixed cells with the L offset satellite-fixed cells for each particular satellite being indexed by a number l=1, . . . , L, with the satellite-fixed cells and the offset satellite-fixed cells being defined as reference satellite-fixed cells;
b. receiving a call from a source user to a destination user, the call having a particular QoS requirement;
c. acquiring information regarding the source user and the destination user, including a user address and user location;
d. determining the satellite, the satellite-fixed cell, and the satellite-fixed cell slot within the satellite-fixed cell in which the source user is located, said satellite being defined as the source user end-reference satellite;
e. determining the satellite, the satellite-fixed cell, and the satellite-fixed cell slot within the satellite-fixed cell in which the destination user is located, said satellite being defined as the destination user end-reference satellite;
f. determining all paths including, at most, a preset number J of inter-satellite hops, between the source user end-reference satellite and the destination end-user reference satellite;
g. calculating a minimum residual link capacity for each of the plurality of paths determined in step (f);
h. determining, for each offset satellite-fixed cell l=1, . . . , L, a set {kl} of paths that maximize the residual bandwidth at that offset satellite-fixed cell;
i. picking, from each set {kl} of paths determined for each offset satellite-fixed cell, one path p such that the combined set CS of paths for all of the offset satellite-fixed cells minimizes the number of communication link changes necessary to maintain a call between the source user and the end user as the satellites move in their orbits; and
j. reserving at each offset satellite-fixed cell, the bandwidth along the path picked in step i, corresponding to the particular QoS requirement of the call.
The calculation of the minimum residual link capacity for each of the plurality of paths at a given offset satellite-fixed cell l may be further defined by rp(l)=ci(l)xe2x88x92Rp, where ci(l) is the current link capacity of link i at offset satellite-fixed cell l, and where Rp represents the bandwidth required for a new call on path p if the connection is admitted in the offset satellite-fixed cell l, and where             R      p        =                  (                  b          +                      C                          tot              )                                      )                    (                              D            req                    -                      d            ⁢                          (              p              )                                      )              ,
where b represents the token bucket size, Ctot represents the total rate-dependent delay experienced by a packet belonging to the call, Dreq represents the end-to-end delay requirement of each packet, and d(p) represents the end-to-end propagation delay for a chosen path p if the connection is admitted on the offset satellite-fixed cell l.
The picking of a path from each set of {kl} paths may be further defined as including the sub-steps of:
i. picking, for each set of paths {kl} for offset satellite-fixed cells l=1, . . . ,L, a path, where the combined set of picked paths over all of the offset satellite-fixed cells l=1, . . . ,L is defined as a combined set of picked paths CSm, where m=1, . . . ,kL;
ii. determining the total number of link changes HSm required on the combined set of picked paths CS;
iii. repeating sub-steps i and ii for each different combination of paths;
iv. determining an overall reward for each combination set Sm={p1(i1), p2(i2), . . . , pL(iL)}, where i1=1, . . . , k is the path chosen for offset satellite-fixed cell l, by:             reward      ⁢              (                  S          m                )              =                            ∑                      l            =            1                    L                ⁢                              r            p                    ⁢                      (            l            )                              -              W        ·                  H          Sm                      ,
where W is a constant used to weigh the relative importance of having few link changes on the route for the call as offset calls are transitioned, with respect to the balancing of the user traffic;
v. choosing the Sm that maximizes the reward(Sm); and
vi. after a path for every offset satellite-fixed cell l=1, 2, . . . , L has been determined for the connection, reserving the necessary bandwidth for each path to satisfy the QoS requirements along the links forming the paths.
Furthermore, an embodiment of the method of the present invention may be operated on a pre-existing satellite network or may include the provision of such a network.
The apparatus of the present invention includes:
a. means for receiving a call from a source user to a destination user;
b. means for acquiring information for the source user and the destination user, including a user address and user location;
c. means for determining the satellite, the satellite-fixed cell, and the satellite-fixed cell slot within the satellite-fixed cell in which the source user is located, said satellite being defined as the source user end-reference satellite;
d. means for determining the satellite, the satellite-fixed cell, and the satellite-fixed cell slot within the satellite-fixed cell in which the destination user is located, said satellite being defined as the destination user end-reference satellite;
e. means for determining all paths including at most a predetermined number J of inter-satellite hops, between the source user end-reference satellite and the destination end-user reference satellite;
f. means for calculating the minimum residual link capacity for each of the paths determined by the means in (e);
g. means for determining, for each offset satellite-fixed cell l=1, . . . ,L, a set {kl} of paths that maximize the residual bandwidth at that offset satellite-fixed cell; and
h. means for picking, from each set {kl} of paths determined for each offset satellite-fixed cell, one path p such that the combined set CS of paths for all of the offset satellite-fixed cells minimizes the number of communication link changes necessary to maintain a call between the source user and the end user.
The calculation of the minimum residual link capacity for each of the plurality of paths at a given offset satellite-fixed cell l may be further defined by rp(l)=ci(l)xe2x88x92Rp, where ci(l) is the current link capacity of a given link i at offset satellite-fixed cell l, and where Rp represents the bandwidth required for a new call on path p if the connection is admitted in the offset satellite-fixed cell l, and where             R      p        =                  (                  b          +                      C                          tot              )                                      )                    (                              D            req                    -                      d            ⁢                          (              p              )                                      )              ,
where b represents the token bucket size, Ctot represents the total rate-dependent delay experienced by a packet belonging to the call, Dreq represents the end-to-end delay requirement of each packet, d(p) represents the end-to-end propagation delay for a chosen path p if the connection is admitted on the offset satellite-fixed cell l.
The picking of a path from each set of {kl} paths may be further defined by the provision of:
i. means for picking, for each set of paths {kl} for offset satellite-fixed cells l=1, . . . , L, a path, where the combined set of picked paths over all of the offset satellite-fixed cells l=1, . . . ,L is defined as a combined set of picked paths CSm, where m=1, . . . ,kL;
ii. means for determining the total number of link changes HSm required on the combined set of picked paths CS;
iii. means for operating the means of in i and ii for each different combination of paths;
iv. means for determining an overall reward for each combination set Sm={P1(i1), p2(i2), . . . , pL(iL)}, where i1=1, . . . , k is the path chosen for offest satellite-fixed cell l, by:             reward      ⁢              (                  S          m                )              =                            ∑                      l            =            1                    L                ⁢                              r            p                    ⁢                      (            l            )                              -              W        ·                  H          Sm                      ,
where W is a constant used to weigh the relative importance of having few link changes on the route for the call as offset calls are transitioned, with respect to the balancing of the user traffic;
v. means for choosing the Sm that maximizes the reward(Sm); and
vi. a means for reserving the necessary bandwidth for each path to satisfy the QoS requirements along the links forming the paths, after a path for every offset satellite-fixed cell l=1, 2, . . . , L has been determined for the connection.
The apparatus of the present invention optionally includes the provision of a satellite constellation orbiting the earth, said satellite constellation including at:least one orbit, with each one of the at least one orbit including a plurality S of satellites, each indexed by a number s, and communicatively connected by a plurality of communication links, with each particular satellite having a satellite-fixed cell divided, perpendicularly with respect to the orbit of the particular satellite, into a plurality L of satellite-fixed cell slots, with the movement of the plurality S of satellites over the earth being characterized in that the satellite-fixed cell for a satellite indexed at s covers the same area as the satellite-fixed cell of a satellite indexed at s+1 after passing over an area on the earth equivalent to the area of L satellite-fixed cell slots, and with an offset satellite-fixed cell being defined each time the satellite-fixed cell covers the area of one of L satellite-fixed cell slots while moving between the position of the satellite-fixed cell corresponding to a satellite indexed s and the satellite-fixed cell corresponding to a satellite indexed s+1, providing L offset satellite-fixed cells with the L offset satellite-fixed cells for each particular satellite being indexed by a number l=1, . . . , L, with the satellite-fixed cells and the offset satellite-fixed cells being defined as reference satellite-fixed cells.